This invention relates generally to methods and apparatus for controlling digital processing systems involving at least one central processing unit (CPU) and a plurality of application processes to be performed. Specifically, the invention relates to systems and techniques for balancing or distributing CPU load among non-communicating processes in a time-sharing system.
In time-sharing or multitasking environments, many application processes or tasks may, at a given time, compete for processing resources provided by one or more central processing units. While the CPU does not typically execute processes simultaneously, the processes are active in the sense that they share CPU resources, i.e., processing time, until they are completed.
The real-time occupancy of CPU resources by an active application processes is referred to as the CPU "load" attributable to that process. In a time-sharing system, the load attributable to each active application process is often controlled or balanced by the operating system according to a predetermined protocol. The term "load balancing" refers to systems and techniques for allocating CPU resources among active application processes. Load balancing may accomplish different desired objectives. For example, the CPU load attributable to each application process may be governed according to preassigned priority levels. Other load-balancing techniques seek quick execution times for the application processes.
In complex time-sharing or multitasking systems, hundreds of application processes, or tasks, may be in active competition for CPU resources at a given time. Each of these application processes may include hundreds or thousands of sub-tasks. In wireless cellular communication systems, for example, telephone network access is provided through radio communication between mobile subscriber radiotelephones and cell sites located within contiguous geographic areas. Each cell site is equipped with various hardware and software, including radio transceivers, antennas and control equipment to facilitate signal transmission between mobile subscribers and the cell sites. In advanced cellular systems, control of a significant portion of cellular networks may be provided through a single CPU, the resources of which are shared among multiple radio control systems (RCS's) each supporting multiple microcells and each relying on its own resident software support applications. An operating system, for example a UNIX-based operating system, is provided with a scheduler, which is responsible for sharing CPU resources among the RCS's. Within each RCS, software applications processes are provided to control various sub-tasks, such as call processing, translation, and auditing associated with that RCS. These sub-tasks have varying levels of importance or priority. Operating systems like UNIX provide for externally assigned priories for the application processes running under them. Typically, all software application processes of equal priority are allotted equal portions of CPU time by UNIX.
The aforementioned prioritizing techniques for load-balancing may provide inadequate results when applied to time-sharing systems like those employed to control complex wireless communication networks. In such systems, the particular type of functions being addressed at the sub-task level should be considered for proper load-balancing. With known techniques, however, this is not feasible. Typically, memory or processing limitations prevent the operating system from tracking detailed information at the sub-task level. Rather, CPU resources are allotted only with regard to the priorities assigned at the application process level. Known systems therefore provide no capability for monitoring determining which application processes are, at any given time, devoting most of their CPU resource allotment to high priority sub-tasks. Nor do they provide the capability to monitor or determine which application processes are devoting most of their CPU time slice to accomplish low priority sub-tasks. Thus, the completion of high priority tasks in one active application process may be delayed while CPU resources are committed to lower priority tasks in another application process.
The problem becomes more apparent when explained in the context of the wireless communication system example discussed above. Sub-tasks associated with call processing or translation are obviously more important than sub-tasks associated with auditing, maintenance or "housekeeping" functions: a "bottleneck" in call processing might result in delays to subscribers placing calls. Maintenance sub-tasks, on the other hand, are usually designed to fill "idle time" within the CPU time slice allotted to a given process. Call processing and translation are "message driven" processes, that is, they are initiated by external events like subscribers placing calls and the CPU resources they require vary from time to time. From the operating system's perspective, all application processes at a given UNIX priority level are competing for equal slices of CPU time. The operating system provides no way of determining when one RCS is utilizing all of its CPU resource allotment to address call processing, a high-priority function, while another RCS may be utilizing all of its CPU resources only to accomplish less-important auditing or maintenance functions. Thus, CPU resources are not allocated in a manner that favors completion of high-priority functions over low-priority functions at the sub-task level.
It would therefore be desirable to provide a method and apparatus for load-balancing which allocates CPU resources in a manner that favors completion of high-priority functions over low-priority functions at the sub-task level. Such a system would be capable of distributing the CPU load in such a manner that active application processes which are utilizing their CPU resource allotment to complete a relatively small proportion of high-priority sub-tasks will relinquish resources in favor of one or more other active processes that are utilizing their CPU resource allotment to complete a relatively high proportion of high-priority sub-tasks.